package sort;

import org.junit.Test;
import utils.CommonUtil;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_315 {
    private List<Integer> list = new ArrayList<>(); //记录次数，但是这个记录信息和原始数组相关

    //使用归并排序思想，从大到小排序，并记录每个元素的右边有多少元素比它小
    public List<Integer> countSmaller(int[] nums) {
        initList(nums);
        Pair[] pairs= initArray(nums);
        mergeSort(pairs,0,nums.length-1);
        return list;
    }

//    @Test
//    public void countSmaller() {
//        int[] arr = new int[]{5,2,6,1};
//        Pair[] pairs = initArray(arr);
//        initList(arr);
//        Pair[] array= mergeSort(pairs,0,pairs.length-1);
//        System.out.println(CommonUtil.printArray(arr));
//        System.out.println(CommonUtil.printList(list));
//    }

    public void initList(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            list.add(0);
        }
    }

    public Pair[] initArray(int[] nums){
        Pair[] pairs = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            Pair pair = new Pair(i, nums[i]);
            pairs[i] = pair;
        }
        return pairs;
    }

    public Pair[] mergeSort(Pair[] arr,int leftIndex,int rightIndex){
        if (leftIndex==rightIndex){
            return new Pair[]{arr[leftIndex]};
        }
        int center = leftIndex+((rightIndex-leftIndex)>>1);
        return merge(
                mergeSort(arr,leftIndex,center),
                mergeSort(arr,center+1,rightIndex)
        );
    }

    private Pair[] merge(Pair[] arr1, Pair[] arr2) {
        int i=0,j=0,k=0;
        Pair[] result = new Pair[arr1.length+arr2.length];
        while(i<arr1.length && j<arr2.length){
            if (arr1[i].value<=arr2[j].value){      //小于情况
                result[k++]=arr2[j++];
            } else{
//                if (k>center){
//                    list.set(i,list.get(i)+arr2.length-j);
//                }else{  //处于center左边
//
//                }
                list.set( arr1[i].index  ,list.get(arr1[i].index)+arr2.length-j);
                result[k++]=arr1[i++];
            }
        }

        while(i<arr1.length){
            result[k++]=arr1[i++];
        }
        while(j<arr2.length){
            result[k++]=arr2[j++];
        }
        return result;
    }

    class Pair{
        int index;
        int value;
        public Pair(int index,int value){
            this.index=index;
            this.value=value;
        }
    }
}
